package com.java.comprehensive.arithmetic.leecode.tags.stack;

import cn.hutool.json.JSONUtil;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @program: comprehensive-service
 *
 * @description: 下一个更大的元素
 *
 * @author: 窦绍飞
 *
 * @create: 2021-12-16 20:41
 **/
public class LeetCode_496 {

	public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
		int[] nums = new int[nums1.length];
		for (int i = 0; i < nums1.length; i++) {
			int temp = nums1[i];
			for (int i1 = 0; i1 < nums2.length; i1++) {
				if (temp == nums2[i1]) {
					int result = -1;
					if (i1 == nums2.length - 1) {
					} else {
						for (int j = i1 + 1; j < nums2.length; j++) {
							if (temp < nums2[j]) {
								result = nums2[j];
								break;
							}
						}
					}
					nums[i] = result;
					break;
				}
			}
		}
		return nums;
	}

	public static int[] nextGreaterElementTwo(int[] nums1, int[] nums2) {
		Map<Integer, Integer> map = new HashMap<>(16);
		Stack<Integer> stack = new Stack<>();
		// 倒叙遍历nums2 为了让 到这把元素放入stack 在放入的过程中比较 只把 在右边有比自己大的元素放入 stack 直接找stack
		// 就知道nums1有没有比自己大的了
		for (int i = nums2.length - 1; i >= 0; i--) {
			int num = nums2[i];
			while (!stack.empty() && stack.peek() <= num) {
				stack.pop();
			}
			map.put(num, stack.isEmpty() ? -1 : stack.peek());
			stack.push(num);
		}
		for (int i = 0; i < nums1.length; i++) {
			Integer integer = map.get(nums1[i]);
			nums1[i] = integer;
		}
		System.out.println(JSONUtil.parse(stack));
		return nums1;
	}

	public static void main(String[] args) {
		// int[] nums1 = { 1, 3, 5, 2, 4 }, nums2 = { 6, 5, 4, 3, 2, 1, 7 };
		int[] nums1 = { 4, 2, 1 }, nums2 = { 1, 3, 4, 2 };
		int[] ints = nextGreaterElementTwo(nums1, nums2);
		System.out.println(Arrays.toString(ints));
	}
}
